互质 欧拉函数

算法基础课 第四章 数学知识(二) 0~46min

image-088125c2 
int phi(int x)

{

    int res = x;

    for (int i = 2; i <= x / i; i ++ )

        if (x % i == 0)

        {

            res = res / i * (i - 1);

            while (x % i == 0) x /= i;

        }

    if (x > 1) res = res / x * (x - 1);

    return res;

}

⬅️ 约数问题 🏠 00-刷题理模型 ➡️ x的因子链